import java.util.TreeSet;
import java.util.HashSet;
import java.util.TreeMap;
import java.util.ArrayList;

/**
 *
 * @author Zuzana Krejcova
 */
public abstract class NaRedukovanou
{
    public static Gramatika transformuj(Gramatika g) throws Exception
    {
        Gramatika ret = eliminujNedosazitelneSymboly(eliminujNenormovaneNetermy(g));
        ret.bezNepouzitelnych = true;
        return ret;
    }

    /**
     * Odebere z gramatiky nenormovane, redundantni neterminaly: X, !(X=>+w).
     * @return Gramatika bez nenormovanych neterminalu, s upravenymi pravidly.
     * Koren je null, pokud se nedostal mezi neterminaly
     */
    public static Gramatika eliminujNenormovaneNetermy(Gramatika g) throws Exception
    {
        TreeSet<String> netermy = new TreeSet();
        TreeSet<String> pomocneNetermy = new TreeSet();
        TreeSet<String> dosazeneSymboly = new TreeSet(g.terminaly); //terminaly a pouzitelne neterminaly
        String novyKoren = new String(g.koren);
        TreeMap<String,HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        TreeSet<String> termy = new TreeSet(g.terminaly);

        // uprava neterminalu
        do
        {
            pomocneNetermy.addAll(netermy);
            dosazeneSymboly.addAll(pomocneNetermy);
            for (String neterm : g.pravidla.keySet())
            {
                if (jdeDerivovatNaTermy(g.pravidla.get(neterm), dosazeneSymboly)) netermy.add(neterm);
            }
        } while (!pomocneNetermy.containsAll(netermy));

        // uprava pravidel
        HashSet<ArrayList<String>> praveStrany = new HashSet();
        for (String neterm : g.pravidla.keySet())
        {
            if (netermy.contains(neterm))
            {
                for (ArrayList<String> jednaPravaStrana : g.pravidla.get(neterm)) //vyber jen pouzitelne prave strany pravidla
                {
                    if (jeZDosazenychSymbolu(jednaPravaStrana, dosazeneSymboly)) praveStrany.add(jednaPravaStrana);
                }
                novaPravidla.put(neterm, new HashSet(praveStrany));
                praveStrany.clear();
            }
        }

        if (!netermy.contains(novyKoren)) throw new Exception("Gramatika generuje prazdny jazyk. Netransformuji.");
        return new Gramatika(netermy, termy, novyKoren, novaPravidla);
    }

    /**
     * Odebere z gramatiky nedosazitelne symboly - terminaly i neterminaly.
     * @return Gramatika bez nedosazitelnych symbolu
     */
    public static Gramatika eliminujNedosazitelneSymboly(Gramatika g)
    {
        TreeSet<String> netermy = new TreeSet();
        TreeSet<String> pomNetermy = new TreeSet();
        TreeSet<String> termy = new TreeSet();
        TreeSet<String> dosazeneSymboly = new TreeSet();
        String novyKoren = new String(g.koren);
        TreeMap<String,HashSet<ArrayList<String>>> novaPravidla = new TreeMap();
        netermy.add(novyKoren);
        pomNetermy.add(novyKoren);

        do
        {
            dosazeneSymboly.addAll(termy);
            dosazeneSymboly.addAll(netermy);

            // hledani dosazitelnych symbolu
            for (String neterm : netermy)
            {
                if (g.pravidla.get(neterm) != null)
                {
                    novaPravidla.put(neterm, g.pravidla.get(neterm)); //a uprava pravidel zaraz
                    for (ArrayList<String> pravaStrana : g.pravidla.get(neterm))
                    {
                        for (String symbol : pravaStrana)
                        {
                            if (g.neterminaly.contains(symbol))
                            {
                                pomNetermy.add(symbol);
                            } else
                            {
                                if (!symbol.equals("\u03B5")) termy.add(symbol);
                            }
                        }
                    }
                }
            }
            netermy.addAll(pomNetermy);
        } while (!dosazeneSymboly.containsAll(termy) || !dosazeneSymboly.containsAll(netermy));
        return new Gramatika(netermy, termy, novyKoren, novaPravidla);
    }

    /**
     * Kontroluje, jestli jde neterminal prepsat na retezec jiz pridanych symbolu.
     * @param neterm
     * @param praveStrany
     * @return
     */
    private static boolean jdeDerivovatNaTermy(HashSet<ArrayList<String>> praveStrany, TreeSet<String> dosazeneSymboly)
    {
        for (ArrayList<String> jednaPravaStrana : praveStrany)
        {
            if (jednaPravaStrana.get(0).equals("\u03B5")) return true;
            if (jeZDosazenychSymbolu(jednaPravaStrana, dosazeneSymboly)) return true;
        }
        return false;
    }

    /**
     * Kontroluje, zda jsou vsechny symboly jedne prave strany pravidla v dosud
     * pridanych dosazitelnych symbolech.
     * @param jednaPravaStrana
     * @param dosazeneSymboly
     * @return
     */
    private static boolean jeZDosazenychSymbolu(ArrayList<String> jednaPravaStrana, TreeSet<String> dosazeneSymboly)
    {
        for (int i=0;i<jednaPravaStrana.size();i++)
        {
            if (!dosazeneSymboly.contains(jednaPravaStrana.get(i))) return false;
        }
        return true;
    }
}
